package com.gitee.ywj1352.leecode;

/**
 * Created by wenjie.yang on 2019/7/24.
 */
public class DynamicPlan {


    //weight: 物品重量，n: 物品个数，w: 背包可承载重量
    public static int knapsack(int[] weight, int n, int w) {
        boolean[][] stat = new boolean[n][w + 1];
        stat[0][0] = true;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < w; j++) {//我不把第i个放入背包
                //因为我这里没有放的决策 所以这里 的 w 肯定和我上一步的一样
                if (stat[i - 1][j] == true) stat[i][j] = stat[i - 1][j];
            }
            for (int j = 0; j <= w - weight[i]; j++) {//我把第i个放入背包 我最多 是能放9个
                if (stat[i - 1][j] == true) {
                    stat[i][j + weight[i]] = true;// 给这里的重量 置为 true
                }
            }
        }
        for (int i = w; i >= 0; i--) {
            if (stat[n - 1][i] == true) return i;
        }
        return 0;
    }


    /**
     * 在给定 m \times nm×n 的矩阵中，我们需要找到在矩阵中由 1 组成的最大正方形。
     * 换句话说，我们需要在矩阵中找到由 1 组成最大连通的正方形，并返回其面积。
     * 1 0 1 1 1
     * 1 0 1 1 1
     * 1 1 1 1 1
     * 1 0 0 1 0
     *
     * @param matrix
     * @return
     */
    public static int maximalSquare(char[][] matrix) {
        //初始化二维数组大小
        int rows = matrix.length;
        int cols = matrix.length > 0 ? matrix[0].length : 0;
        int[][] dp = new int[rows+1][cols+1];//因为要 想当于初始化了 第一列
        int maxSqe = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    maxSqe = Math.max(dp[i][j], maxSqe);
                }
            }
        }
        return maxSqe * maxSqe;
    }


    /**
     * https://leetcode-cn.com/problems/maximal-rectangle/
     * 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
     * 输入:
     * [
     *   ["1","0","1","0","0"],
     *   ["1","0","1","1","1"],
     *   ["1","1","1","1","1"],
     *   ["1","0","0","1","0"]
     * ]
     * 输出: 6
     * @param matrix
     * @return
     */
    public static int maximalRectangle(char[][] matrix) {
        //初始化二维数组大小
        int rows = matrix.length;
        int cols = matrix.length > 0 ? matrix[0].length : 0;
        int[][] dp = new int[rows+1][cols+1];//因为要 想当于初始化了 第一列
        int[][] sdp = new int[rows+1][cols+1];//因为要 想当于初始化了 第一列
        int[] minCols = new int [cols+1];
        int[] minRows = new int [cols+1];
        int maxSq = -1;
        //初始化
        for (int i =1 ;i<=rows;i++){
            for (int j =1 ;j<=cols;j++){
                if(matrix[i - 1][j - 1] == '1' ){
                    dp[i][j] = dp[i][j-1] + 1;
                    minCols[j] = Math.min(minCols[j]==0? Integer.MAX_VALUE:minCols[j],dp[i][j]);
                }
            }
        }

        for (int i =1 ;i<=cols;i++){//列
            for (int j =1 ;j<=rows;j++){//行
                if(matrix[j - 1][i - 1] == '1' ){
                    sdp[j][i] = sdp[j][i-1] + 1;
                    minRows[i] = Math.min(minRows[i]==0? Integer.MAX_VALUE:minRows[i],sdp[j][i]);
                }
            }
        }

        // 计算面积
        for (int i =1 ;i<=rows;i++){
            for (int j =1 ;j<=cols;j++){
                if( sdp[i][j] !=0 && dp[i][j] !=0){
                    maxSq = Math.max(maxSq,minRows[i] * minCols[j]);
                }
            }
        }
        return maxSq;
    }


    public static void main(String[] args) {
//        int knapsack = knapsack(new int[]{2, 2, 4, 6, 3,3,5}, 5, 19);
//        System.out.println(knapsack);
        /**
         * 1 0 1 0 0
         * 1 0 1 1 1
         * 1 1 1 1 1
         * 1 0 0 1 0
         */
        char[][] arr = {{'1', '0', '1', '1', '1'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}};
        int i = maximalRectangle(arr);
        System.out.println(i);
    }


}
